//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
// Related Topics 链表 双指针 
// 👍 1787 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.HashMap;
import java.util.Map;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution19 {
    /**
     * 解题思路：
     * 1.用map保存链表下标和链表节点的关系
     * 2.在map中查找对应的链表，然后做处理
     *
     * 解答成功:
     * 			执行耗时:1 ms,击败了6.63% 的Java用户
     * 			内存消耗:39.6 MB,击败了7.29% 的Java用户
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        Map<Integer, ListNode> map = new HashMap<>();
        int index = 0;

        ListNode tmp = head;
        while(tmp != null) {
            map.put(index++, tmp);
            tmp = tmp.next;
        }

        int targetIndex = index - n;
        ListNode targetNode = map.get(targetIndex);
        if(targetIndex == 0) {
            return targetNode.next;
        }

        ListNode prevNode = map.get(targetIndex - 1);
        prevNode.next = targetNode.next;
        return head;
    }

    /**
     * 解题思路：
     * 1. 设置一个虚拟头节点root，其下一个节点是head， 设置两个指针指向这个虚拟头节点
     * 2. 先startNode移动n次，在判断startNode.next不为空时同时移动start和end指针
     * 3. 当startNode.next为空，说明已到达最后一个节点，此时end指针指向目标节点的前一个节点
     * 4. end.next = end.next.next 即链表的节点删除一位
     * 5. 返回root.next节点即可
     *
     * 解答成功:
     * 			执行耗时:0 ms,击败了100.00% 的Java用户
     * 			内存消耗:39.5 MB,击败了9.24% 的Java用户
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode root = new ListNode(0);
        root.next = head;

        ListNode startNode = root;
        ListNode endNode = root;
        while(n>0) {
            startNode = startNode.next;
            n--;
        }

        while(startNode.next != null) {
            startNode = startNode.next;
            endNode = endNode.next;
        }

        endNode.next = endNode.next.next;
        return root.next;
    }

    public static void main(String[] args) {
        ListNode listNode11 = new ListNode(1);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(3);
        ListNode listNode14 = new ListNode(4);
        ListNode listNode15 = new ListNode(5);
        listNode14.next = listNode15;
        listNode13.next = listNode14;
        listNode12.next = listNode13;
        listNode11.next = listNode12;

//        new Solution19().removeNthFromEnd(listNode11, 2);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
